package permutaton;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: javase
 * @description:  数组元素重复情况，先排序再递归时比较与上一个数是否相同，相同跳过
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 * 示例 1：
 * 输入：nums = [1,1,2]
 * 输出：
 * [[1,1,2],
 * [1,2,1],
 * [2,1,1]]
 * @author: luolidong
 * @create: 2021-06-13 10:09
 * @version: 1.0
 */
public class Demo1 {
    boolean[] isVisited;

    public List<List<Integer>> permuteUnique(int[] nums) {
        isVisited = new boolean[nums.length];
        List<List<Integer>> list = new ArrayList<>();
//        先排序，保证相同元素相邻
        Arrays.sort(nums);
        backtrack(list, new ArrayList<>(), nums);
        return list;

    }

    public void backtrack(List<List<Integer>> list, List<Integer> clist,
                          int[] nums) {
        if (clist.size() == nums.length) {
            list.add(new ArrayList<>(clist));
            return;
        }
//        通过维护一个临时变量，记录上一个数
        int pre = -11;
        for (int i = 0; i < nums.length; i++) {
            if (isVisited[i] || pre == nums[i]) continue;
            isVisited[i] = true;
            clist.add(nums[i]);
            backtrack(list, clist, nums);
            clist.remove(clist.size() - 1);
            isVisited[i] = false;
            pre = nums[i];
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 1, 3};
        List<List<Integer>> list = new Demo1().permuteUnique(nums);
        System.out.println(list);
    }
}
